/*
	@file heap_gauss

	@brief Heap implementation by gauss

	@author gauss
*/

/*
Description:
	Memory blocks metadata (sizes and tags) is stored in map
	container. Key in it is pointer to block, so blocks are arranged
	sequentially by address. Information about free space is not stored anyhow.
	Search function (first_fit) iterates through this sequence of blocks and
	returns (if finds place) address of place and iterator on previous block (to
	boost insertion in map). free just finds and erases block from map.

	Algorithm is going to be changed somehow soon to boost performance.
*/

//todo: maybe create new .h file with conditional compilation flags
//		try to unite neighbouring blocks in search
//		maybe use set instead of map and store tag and size in memory
//		add history and logging
//		add poisoning and optimizations in realloc
//		somehow use alloc_optimize_mem

#include<stdio.h>
#include"../../api/heap.h"
#include"heap_gauss.h"

//macro for error output
#define Err printf

#ifdef _DEBUG
	//macro for debug output
	#define Dbg printf
#else//_DEBUG
	#define Dbg
#endif//_DEBUG

//round up x to ALIGN*n
#define ROUND_ALIGN(x) (x)=((x)+ALIGN-1)&(~(ALIGN-1))

heap_gauss::heap_gauss(size_t total,alloc_flags flag)
	:heap876(total,flag,"gauss")
{
#ifdef _STUB
	return;
#endif//_STUB
	if(!(Memory=malloc(ROUND_ALIGN(total_limit))))
	{
		Err("[heap]heap_gauss:couldn't get memory,total=%d\n",total_limit);
		throw bad_alloc();
	}
	AllocatedSize=0;
	Mutex=CreateMutex(NULL,false,NULL);
	if(flag&alloc_debug)//mark up all memory as free
		memset(Memory,POISON_FREE,total_limit);
}

heap_gauss::~heap_gauss()
{
#ifdef _STUB
	return;
#endif//_STUB
	if(AllocatedSize!=0)
	{
		Err("[heap]~heap_gauss:not empty,sz=%d\n",AllocatedSize);
#ifdef _DEBUG
		dump_all_blocks();
#endif//_DEBUG
	}
	CloseHandle(Mutex);
	std::free(Memory);
}

heap_gauss::FitPlace heap_gauss::first_fit(size_t sz)
{
	FitPlace result={NULL,Blocks.begin()};
	if(Blocks.empty())//if there are no blocks
	{
		result.ptr=Memory;
		return(result);
	}
	map_iterator i;
	size_t ptr=(size_t)(Memory);
	for(i=Blocks.begin();i!=Blocks.end();i++)//iterate through blocks
	{
		if(sz<=((size_t)(i->first)-ptr))
		{
			result.ptr=(void*)ptr;
			result.pos=i;
			return(result);
		}
		ptr=(size_t)(i->first)+i->second.size;//try getting the next pointer
	}
	if(sz<=(size_t)Memory+total_limit-ptr)//check after the last block
	{
		result.ptr=(void*)ptr;
		result.pos=i;
	}
	return(result);//result.ptr is NULL if no place found
}

void* heap_gauss::alloc(size_t sz,unsigned int tag)
{
#ifdef _STUB
	return(malloc(sz));
#endif//_STUB
	if(sz==0)
		return(NULL);
	WaitForSingleObject(Mutex,INFINITE);
	if((AllocatedSize+(ROUND_ALIGN(sz)))>total_limit)//certainly not enough space
	{
		Err("[heap]alloc:failed to alloc{sz=%d,tag=%d},al_sz=%d,total=%d\n",
			sz,tag,AllocatedSize,total_limit);
		ReleaseMutex(Mutex);
		return(NULL);
	}
	FitPlace place=first_fit(sz);
	void *ptr=place.ptr;
	if(ptr==NULL)
	{
		Err("[heap]alloc:failed to alloc{sz=%d,tag=%d},al_sz=%d,total=%d\n",
			sz,tag,AllocatedSize,total_limit);
		ReleaseMutex(Mutex);
		return(ptr);
	}
	if(flag&alloc_debug)
		for(int *m=(int*)ptr,*end=(int*)((size_t)ptr+sz);m<end;m++)
		{
			if(*m!=POISON_FREE)//check if memory is free
			{
				Err("[heap]alloc:memory at %p is not free,ptr=%p,sz=%d\n",
					m,ptr,sz);
				ReleaseMutex(Mutex);
				return(NULL);
			}
			*m=POISON_ALLOC;//mark up memory as allocated
		}
	MemoryBlock b={sz,tag};
	Blocks.insert(place.pos,make_pair(ptr,b));//remember the block
	AllocatedSize+=sz;
	ReleaseMutex(Mutex);
	return(ptr);
}

void heap_gauss::free(map_iterator b)
{
	if(flag&alloc_debug)//mark up memory as free
		memset(b->first,POISON_FREE,b->second.size);
	AllocatedSize-=b->second.size;
	Blocks.erase(b);
}

void heap_gauss::free(void* ptr)
{
#ifdef _STUB
	::free(ptr);
	return;
#endif//_STUB
	if(ptr==NULL)
		return;
	WaitForSingleObject(Mutex,INFINITE);
	map_iterator b=Blocks.find(ptr);
	if(b==Blocks.end())
		Err("[heap]free:no such block{ptr=%p}\n",ptr);
	else
		free(b);
	ReleaseMutex(Mutex);
}

void heap_gauss::free_all(unsigned int tag)
{
	if(flag&heap876::alloc_tagged)
	{
		WaitForSingleObject(Mutex,INFINITE);
		for(map_iterator i=Blocks.begin(),j;i!=Blocks.end();)
		{
			j=i++;
			if(j->second.tag==tag)
				free(j);
		}
		ReleaseMutex(Mutex);
	}
}

#ifdef _DEBUG//debugging stuff

void heap_gauss::dump_memory(void *ptr,size_t length)
{
	length=length/sizeof(int)+((length%sizeof(int))?1:0);
	if(((size_t)ptr<(size_t)Memory)
		||((size_t)ptr+length>(size_t)Memory+total_limit))
	{
		Dbg("dump_memory{ptr=%p,l=%d}:out of bounds\n",ptr,length);
		return;
	}
	Dbg("=====begin of memory dump=====\n");
	for(size_t i=0;i<length;i++)
		Dbg("\t%p\n",((int*)ptr)[i]);
	Dbg("======end of memory dump======\n");
}

void heap_gauss::dump_memory()
{
	Dbg("Dumping all: Memory=%p,total=%d\n",Memory,total_limit);
	dump_memory(Memory,total_limit);
}

void heap_gauss::dump_block(void *ptr)
{
	map_iterator b=Blocks.find(ptr);
	if(b==Blocks.end())
		Dbg("block{ptr=%p}:not found\n",ptr);
	else
		Dbg("block{ptr=%p}:sz=%d,tag=%d\n",ptr,b->second.size,b->second.tag);
}

void heap_gauss::dump_all_blocks()
{
	Dbg("=====begin of blocks dump=====\n");
	for(map_iterator i=Blocks.begin();i!=Blocks.end();i++)
		Dbg("\tptr=%p,sz=%d,tag=%d\n",i->first,i->second.size,i->second.tag);
	Dbg("======end of blocks dump======\n");
}

void heap_gauss::dump_memory_map(bool tags)
{
	Dbg("===begin of memory map dump===\n");
	map_iterator last=Blocks.end(),i,j;
	last--;
	size_t free;
	for(i=Blocks.begin();i!=last;)
	{
		if(tags)
			Dbg("|###%d,%d###|",i->second.size,i->second.tag);
		else
			Dbg("|###%d###|",i->second.size);
		j=i++;
		free=(size_t)(i->first)-((size_t)(j->first)+j->second.size);
		if(free!=0)
			Dbg("    %d    ",free);
	}
	if(tags)
		Dbg("|###%d,%d###|",last->second.size,last->second.tag);
	else
		Dbg("|###%d###|",last->second.size);
	free=(size_t)Memory+total_limit-((size_t)(last->first)+last->second.size);
	if(free!=0)
		Dbg("    %d    |",free);
	Dbg("\n====end of memory map dump====\n");
}

#endif//_DEBUG
